76. 最小覆盖子串

Similar Question

Solution Tips

方案一: 固定窗口法

  var minWindow = function (s, t) {
    const len = s.length;
    // p的哈希表
    const tMap = getMap(t);
    // 要最小的，从k开始增加长度
    for (let k = t.length; k < s.length + 1; k++) {
      const subMap = getMap(s.slice(0, k));
      for (let i = 0, j = i + k; j < len + 1; i++, j++) {
        let match = true;
        for (const [key, val] of Object.entries(tMap)) {
          // 有这个字母，且数量大于等于val
          if (subMap.hasOwnProperty(key)) {
            if (subMap[key] < val) {
              match = false;
              break;
            }
          } else {
            match = false;
            break;
          }
        }
        if (match) return s.slice(i, j);
        subMap[s[i]]--;
        if (subMap[s[j]] === 0 || subMap[s[j]] === undefined) subMap[s[j]] = 1;
        else subMap[s[j]]++;
      }
    }
    return "";
    function getMap(str) {
      const map = {};
      for (let i = 0; i < str.length; i++) {
        const key = str[i];
        if (map.hasOwnProperty(key)) map[key]++;
        else map[key] = 1;
      }
      return map;
    }
  };
  let s = "ADOBECODEBANC",
    t = "ABC";
  console.log(minWindow(s, t));

方案二: 滑动窗口 + 哈希表

滑动窗口法可以减少很多多余的判断

滑动窗口算法的思路是这样：

1. 我们在字符串 S 中使用双指针中的左右指针技巧，初始化 left = right = 0，把索引闭区间 [left, right] 称为一个「窗口」。
2. 我们先不断地增加 right 指针扩大窗口 [left, right]，直到窗口中的字符串符合要求（包含了 T 中的所有字符）。
3. 此时，我们停止增加 right，转而不断增加 left 指针缩小窗口 [left, right]，直到窗口中的字符串不再符合要求（不包含 T 中的所有字符了）。同时，每次增加 left，我们都要更新一轮结果。
4. 重复第 2 和第 3 步，直到 right 到达字符串 S 的尽头。

这个思路其实也不难，第 2 步相当于在寻找一个「可行解」，然后第 3 步在优化这个「可行解」，最终找到最优解。左右指针轮流前进，窗口大小增增减减，窗口不断向右滑动。

var minWindow = function (s, t) {
    // 窗口结构是哈希表? 哈希表没办法瞬间判断?
    // 就哈希表就可以了
    if (s.length < t.length) {
        return "";
    }

    const targetMap = {};
    for (let i = 0; i < t.length; i++) {
        if (!targetMap[t[i]]) {
            targetMap[t[i]] = 1;
        }
        else {
            targetMap[t[i]]++;
        }
    }

    const sourceMap = {};
    let res = " ".repeat(s.length);
    let left = 0;
    let right = 0;
    while (left <= right && right < s.length) {
        // 找齐 targetMap 里面的字符, 就用最朴素的遍历来判断是否找齐了, 之后再优化
        while (!findAll()  && right < s.length) {
            // 找到一个
            if (!sourceMap[s[right]]) {
                sourceMap[s[right]] = 1;
            }
            else {
                sourceMap[s[right]]++;
            }
            right++;
        }

        // 这一个瞬间, 从 [left, right], 里面包含了所有的 targetMap 字符
        // 这里开始缩短 left, 同时更新 res
        while (findAll()  && left <= right) {
            if (right - left <= res.length) {
                res = s.slice(left, right)
            }

            sourceMap[s[left]]--;
            left++;

        }
    }

    return res.trim();

    function findAll() {
        let res = true;
        for (const [key, val] of Object.entries(targetMap)) {
            if ((sourceMap[key] || 0) < val) {
                res = false;
                break;
            }
        }

        return res;
    }
};

优化 Match 逻辑

用一个 match 变量, 统计每个元素是否都 match 了, match === targetMatch

var minWindow = function (s, t) {
    const len = s.length;
    // p的哈希表
    const needs = getMap(t);
    const subMap = {};
    let left = 0,
        right = 0;
    let res = "",
        minLen = s.length;
    let match = 0; // 记录已经匹配needs的长度
    while (right < len) {
        const char = s[right];
        if (needs.hasOwnProperty(char)) {
            subMap[char] === undefined ? (subMap[char] = 1) : subMap[char]++;
            // 等于，在等于的那一刻match++，之后再添加也不能增加match的长度 'bb' 'b' ，match最多也就是1
            if (subMap[char] === needs[char]) match++;
        }
        // 不可以等于
        while (match === needs.length && left < len) {
            // 如果长度更小，则更新
            if (right - left < minLen) {
                res = s.slice(left, right + 1);
                minLen = right - left + 1;
            }
            // 再次判断是否符合
            const char = s[left];
            if (needs.hasOwnProperty(char)) {
                subMap[char]--;
                // 在小于的那一刻--
                if (subMap[char] < needs[char]) match--;
            }
            left++;
        }
        right++;
    }
    return res;

    function getMap(str) {
        const map = {};
        map.length = 0;
        for (let i = 0; i < str.length; i++) {
            const key = str[i];
            if (map.hasOwnProperty(key)) map[key]++;
            else {
                map[key] = 1;
                map.length++;
            }
        }
        return map;
    }
};